Теорема о числе перемещений

Перестановка $\sigma \in S_n$ называется **перемещением**, если $\sigma(i) \neq i$ для всех $i$. Пусть $D(n)$ — число перемещений $n$-элементного множества.

$$D(n) = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}$$

Положим $A_k = \{\sigma \in S_n \mid \sigma(k) = k\}$. На перестановку $\sigma \in A_k$ можно смотреть как на перестановку множества $\{1, \dots, n\} \setminus \{k\}$, доопределенную условием $\sigma(k) = k$, следовательно $|A_k| = (n-1)!$. Аналогично, для любого $X \subseteq \{1, \dots, n\}$, мощность пересечения $|\bigcap_{k \in X} A_k| = (n-|X|)!$. Применим симметричный принцип включений-исключений для нахождения числа перемещений $D(n) = |S_n \setminus \bigcup_{k=1}^{n} A_k|$: $$D(n) = \sum_{i=0}^{n} (-1)^i \binom{n}{i} (n-i)! = \sum_{i=0}^{n} (-1)^i \frac{n!}{i!(n-i)!}(n-i)! = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}$$ $\square$